package com.atwy.algorithm;

import java.util.Arrays;

/**
 * @Author: 小王子火
 * @Date: 2022/3/12
 * KMP算法：字符串查找算法，在一个文本串S内查找一个模式串P出现的位置。
 * 利用之前判断过的信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，
 * 每次回溯时，通过next数组找到，前面匹配过的位置，这样相比暴力匹配省去大量时间
 * <p>
 * 部分匹配表
 * 先介绍前缀和后缀，举例：
 * 字符串："bread"
 * 前缀：b,br,bre,brea -- 前缀不包含最后一个字符
 * 后缀：read,ead,ad,d -- 后缀不包含第一个字符
 * <p>
 * 部分匹配表，就是前缀和后缀的最长的共有元素的长度。以"ABCDABD"为例：
 * -- "A" 的前缀和后缀都是空集，共有元素的长度为0；
 * -- "AB" 的前缀是A,后缀是B，共有元素的长度为0；
 * -- "ABC" 的前缀是A,AB,后缀是BC,C,共有元素的长度为0；
 * --..
 * -- "ABCDA"的前缀是A,AB,ABC,ABCD,后缀是BCDA,CDA,DA,A,共有元素为"A",长度为1.
 * ...这里就不一一列举了
 * <p>
 * 总之，这样就能得出一个int[] next
 * next[0],指"A"对应的匹配值 0；
 * next[1],指"AB"对应的匹配值 0；
 * ...
 * next[4],指"ABCDA"对应的匹配值 1；
 */
public class Kmp {
    public static void main(String[] args) {
        testKmp();
    }

    private static void testKmp() {
        // 文本串
        String s = "BBC ABCDAB ABCDABCDABDE";
        // 模式串
        String p = "ABCDABD";
        //p="AE";
        int index = kmpSearch(s, p);
        System.out.println("文本串："+s+",模式串："+p+"，匹配的位置是：index="+index);

    }

    /**
     * @param s 文本串
     * @param p 模式串
     * @return 匹配成功时返回，匹配位置第一个字符的下标；匹配不成功返回-1
     */
    public static int kmpSearch(String s, String p) {
        if (s == null || p == null) {
            return -1;
        }
        int[] next = getNextArray(p);
        System.out.println("模式串："+p+"，最大长度表是："+Arrays.toString(next));
        // 根据最大长度表：字符串失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
        // 根据next数组：失配时，模式串向右移动的位数：失配字符所在位置 - 失配字符对应的next值
        // 模式串向右移动，指向模式串的j就是向左回溯
        for (int i = 0, j = 0; i < s.length() ; i++) {
            while (j>0 && s.charAt(i) != p.charAt(j)){
                // 当前j不匹配，也就是j之前的字符是匹配的，按照最大长度表找出回溯位置，可知回溯位置之前的字符肯定是匹配
                // 然后再比较回溯位置的字符与i字符是否相同，重复此过程，直到j为0或者找到相等的
                j = next[j-1];
            }
            if (s.charAt(i) == p.charAt(j)) {
                j++;
            }
            // 说明p模式串完全匹配了
            if(j == p.length()){
                return i-j+1;
            }
        }

        return -1;
    }

    /**
     * 这里求的实际是 最大长度表
     *
     * @param s
     * @return
     */
    private static int[] getNextArray(String s) {
        if (s == null) {
            return null;
        }
        // 这里next数组的含义：当前字符的前缀后缀最大公有长度
        int[] next = new int[s.length()];

        // 一个字符时，前缀和后缀都是空集，一定为0
        next[0] = 0;
        // i指向后缀的最后一个字符；
        // 理解这个j的含义：如果存在前缀==后缀字符串那 j指向前缀的最后一个字符
        // i保持从s模式串的第二个字符开始移动，每次移动1，可以当作next数组的下标
        int i = 1, j = 0;
        while (i < s.length()) {

            if (s.charAt(i) == s.charAt(j)) {
                j++;
                next[i] = j;
            } else if (j != 0) {
                // 重置j的位置,i不变，目的是缩小匹配长度进行查找
                // 为啥j要缩小为next[j]? 其实很简单，想想j是怎么从0跑到现在位置的？！！！！这是关键

                // j之所以能从0增加到先在这个位置，因为字符串s的
                // 前段Q：0  ,1  ,...,j-1
                // 后段H：j+1,j+2,...,i-1,这两段字符串是相等的。这里字符串的表述不严谨，但只为理解
                // 但现在j位置的字符和i位置的字符不相等了，但可能存在缩小长度的字符串相等，关键就在于怎么找这个
                // 利用前段Q == 后段H这个已知信息！！！
                // 我们假设，字符串P = Q，则P = H
                // 前段Q去掉最后一个字符变成0,1,...,j-2
                // 后段H去掉首字符变成 j+2,...i-1
                // 如果这两段是相等的，是不是说明：字符串P的前缀后缀最大长度是length{0,1,...,j-2},
                // 这不就是next[p.length-1]的大小嘛
                // 如果Q去掉最后两个字符 才和 H去掉最前面两个字符，说明字符串P的前缀后缀最大长度是length{0,1,...,j-3}
                // 这还是 next[p.length-1]的含义啊

                // 我们回到Q去掉一个字符 == H去掉首字符，即 {0,1,...,j-2} = {j+2,...i-1}
                // 此时如果 j-1位置的字符 = i位置的字符，那此时的next[i] = j-1

                // 所以j回溯的位置怎么定？next[j]表示0,1,...,j-1这个字符串前缀后缀最大公有元素长度
                j = next[j];
                // 回溯之后，i不能变，要再找找
                continue;
            }
            i++;

        }
        return next;
    }

    /**
     * next数组：各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。
     *
     * @param s
     * @return
     */
    private static int[] getNext(String s) {
        if (s == null) {
            return null;
        }
        int[] next = new int[s.length()];
        // 第一个字符前面没有字符，所有初始化为-1；  其实next[1]也是已知的next[1]=0
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < s.length() - 1) {
            // s.charAt(j)表示后缀，s.charAt(k)表示前缀
            if (k == -1 || s.charAt(j) == s.charAt(k)) {
                ++k;
                ++j;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
}
